This invention relates generally to computer networks and, more particularly, to the efficient deployment of router resources when rendering route selection decisions after restarts in a computer network.
A computer network is a geographically distributed collection of interconnected communication links for transporting data between nodes, such as computers. Many types of computer networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). The nodes typically communicate by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate node, called a router, to extend the effective xe2x80x9csizexe2x80x9d of each network. Since management of a large system of interconnected computer networks can prove burdensome, small groups of computer networks may be maintained as autonomous systems or routing domains. The networks within a routing domain are typically coupled together by conventional xe2x80x9cintradomainxe2x80x9d routers. Yet it still may be desirable to increase the number of nodes capable of exchanging data; in this case, xe2x80x9cinterdomainxe2x80x9d routers executing interdomain routing protocols are used to interconnect nodes of the various autonomous systems. An example of an interdomain routing protocol is the Border Gateway Protocol (BGP) which performs routing between autonomous systems by exchanging routing and reachability information among the interdomain routers of the systems. The interdomain routers configured to execute the BGP protocol, called BGP routers, maintain routing tables, transmit routing update messages and render routing selection decisions based on routing metrics.
Specifically, each BGP router maintains a routing table that lists feasible paths to a particular destination. Periodic refreshing of the routing table is generally not performed; however, BGP peer routers residing in the autonomous systems exchange routing information under certain circumstances. For example, when a BGP router initially connects to the network, the peer routers exchange the entire contents of their routing tables with that router. Thereafter when changes occur to those contents, the routers exchange only those portions of their routing tables that change in order to update their peers"" tables. These update messages, which are sent in response to routing table changes, advertise routing changes with respect to a particular destination. The BGP routing protocol is well-known and described in detail in Request for Comments (RFC) 1771, by Y. Rekhter and T. Li (1995), and Interconnections, Bridges and Routers, by R. Pearlman, published by Addison Wesley Publishing Company, at pages 323-329 (1992), all disclosures of which are hereby incorporated by reference.
Broadly stated, a BGP router generates routing update messages for a neighboring peer router by xe2x80x9cwalking-throughxe2x80x9d the routing table and applying appropriate routing policies. A routing policy is information that enables a BGP router to rank routes according to filtering and preference (i.e., the xe2x80x9cpreferredxe2x80x9d route). Routing updates provided by the update message allow BGP routers of the autonomous systems to construct a consistent view of the network topology. The update messages are sent using a reliable transport, such as the Transmission Control Protocol (TCP), to ensure reliable delivery. TCP is a transport protocol implemented by a transport layer of the Internet Protocol (IP) architecture; the term TCP/IP is commonly used to denote this architecture. The TCP/IP architecture is well known and described in Computer Networks, 3rd Edition, by Andrew S. Tanenbaum, published by Prentice-Hall (1996).
After the TCP transport connection is established, the neighboring BGP routers exchange various messages defined by the BGP protocol; in particular, the routers exchange conventional BGP OPEN and KEEPALIVE messages. The OPEN message sets forth parameters that allow the routers to identify themselves and to negotiate various exchange parameters, whereas the initial KEEPALIVE message transfer typically confirms acceptance of the OPEN message exchange. As used herein, the term restart denotes establishment of a reliable peer connection between the neighboring routers.
Upon a restart, the initial transfer among the BGP neighbors involves an exchange of their entire or xe2x80x9cfullxe2x80x9d BGP routing tables. A full routing table exchange comprises the transfer of a complete set of preferred paths to each destination stored in each neighbor""s BGP routing table. In addition to the routing table, each router contains a forwarding table that controls forwarding of packets to, e.g., a next hop. The routing table is used to construct the forwarding table and, as described herein, router resources are required to update those tables.
The initial transfer of the routing table is realized through the use of one or more BGP UPDATE messages. The conventional UPDATE message is generally used to advertise a current route of a neighboring router; as a result, each UPDATE message issued by a BGP neighboring router subsequent to the initial routing information exchange is an incremental update that comprises advertisement of only one or a subset of the preferred paths. The same UPDATE message format is used to exchange both the initial BGP routing table and any incremental changes to that table.
After confirming the OPEN message exchange during the restart, the KEEPALIVE message is periodically issued by a sending peer router to ensure that the receiving peer router xe2x80x9cknowsxe2x80x9d that the sender is alive. Although a router may send KEEPALIVE messages in addition to UPDATE messages, a neighbor that has routes to advertise may send the UPDATE message in lieu of the KEEPALIVE message. Receipt of an UPDATE message by the receiving peer router is, however, an indication that the sending peer router is alive and, thus, obviates the need to send the periodic KEEPALIVE message. A hold time value (i.e., xe2x80x9chold-down timerxe2x80x9d) contained in the OPEN message defines a maximum time period (e.g., number of seconds) that may elapse between receipt of successive KEEPALIVE and/or UPDATE messages by a neighbor.
Once a BGP router receives routing information via the UPDATE message, it performs a BGP route selection process to determine if the newly received route is preferred to the currently used route. That is, the router compares the newly received route to a destination (stored in the message) with the contents of its routing table by essentially xe2x80x9cwalking-throughxe2x80x9d the routing table to locate a route that has the same destination as the new route. Upon finding a match, the router applies the predetermined routing policy to determine which route is preferred by ranking the routes according to local criteria of the router. The local criteria are preferably based on predetermined preference and filtering parameters; for example, the preferred route may be determined based on the length of an autonomous system path. If the new route is preferred to the route stored in the routing table, the router completes the route selection process by updating its forwarding table with the new route and advertising that route to its neighbors, subject to the hold-down timer.
A problem with this conventional approach is that after a restart, the router may receive routing table updates to the same destination from the many different neighbors. For example, assume that router A has three neighbors N1-N3, each of which has a route to a destination D. From A""s point of view, the preferred route is the route advertised (via the UPDATE message) by N1, the next preferred route is the route advertised by N2 and the least preferred route is the route advertised by N3. However, the UPDATE messages received by A from N1-N3 may arrive in various sequences. For example, a first scenario may comprise A initially receiving an UPDATE message from N1, and then from N2 and N3. Since the route to D advertised by N1 is the first route received by A, router A selects that route as the preferred route. Consequently, A loads this route into its routing table, updates its forwarding table with this route and advertises it to its neighbors as the xe2x80x9cpreferredxe2x80x9d route.
Upon receiving an UPDATE message containing the route to D advertised by N2, A xe2x80x9cwalksxe2x80x9d its routing table and finds (as a match to D) the route advertised by N1. Router A compares the two routes according to its local criteria and determines that the route from N2 is no better than the route from N1. Accordingly, router A loads the route from N2 into its routing table, but does not update its forwarding table with that route because the route advertised by N1 is the preferred route. Furthermore, router A does not issue an update to its neighbors for the route from N2. Router A then receives an UPDATE message containing the route advertised by N3, compares that route with the preferred route from N1 stored in its routing table and loads the route advertised by N3 into the routing table. However, A does not update its forwarding table with the route from N3 nor does it generate an UPDATE message for that route because the route from N1 is the preferred route.
A second scenario comprises A first receiving an UPDATE message from N3. Since this is first route to destination D received by A, router A selects this route as its preferred route, updates its routing and forwarding tables with the route and advertises the route from N3 to its neighbors. Router A then receives an UPDATE message from N2 and walks the entire routing table until it discovers a match with the route advertised by N3. Applying the routing policy, A determines that the route from N2 is preferred to the route from N3, so it updates both its routing and forwarding tables with the preferred route from N2, withdraws (either implicitly or explicitly) the route from N3 and instead advertises the route from N2 as the preferred route. Finally, A receives an UPDATE message advertising a preferred route from N1. A walks the routing table, finds a route to D advertised by N2, determines that the route from N1 is preferred, updates its forwarding and routing tables with the preferred route from N1, withdraws the previous route and advertises the new route from N1 as the preferred route.
In the first scenario, router A consumes certain resources when walking the routing table and performing route selection operations. Essentially, router A must execute three (3) independent comparison operations: A must compare the received UPDATE messages, each containing a full set of routes from a neighbor, among themselves whether they are received by A at the same time or at different times. According to the BGP protocol, router A must also update its routing table each time it receives an UPDATE message to establish a record which reflects those routers from which it has received routing updates.
In the second scenario, however, A must update both its routing and forwarding tables in response to each UPDATE message received from its neighbors because each subsequently received xe2x80x9cnewxe2x80x9d route is a preferred route as determined by the route selection process. Moreover, as each new route is selected to be the preferred route, the router A must withdraw the previous route and advertise the preferred route to its neighbors subject to hold-down timer constraints. This scenario results in consumption of substantially more of the router""s resources and contributes to overall routing instability since router A has previously advertised irrelevant routing information to its neighbors.
Therefore, the sequence of one or more UPDATE messages received at a router upon a restart has xe2x80x9cglobalxe2x80x9d implications in that it may impact additional resources consumed not only at the router, but also at its neighbors. It is thus desirable to provide a technique for reducing resource consumption at a router when performing route selection decisions at restart. In addition, it is desirable to provide a technique for deferring BGP route selection procedures at a BGP router until all routing table updates from all neighboring peer routers have been received at the router.
The present invention is directed to a technique for reducing consumption of resources on behalf of a router and its neighboring routers in a computer network by deferring the point at which the router renders a route selection decision. The invention generally pertains to full routing table exchanges among the neighboring routers upon a restart. Specifically, the invention pertains to a technique for deferring route selection in accordance with the Border Gateway Protocol (BGP) until all of the BGP neighboring peer routers finish updating the BGP router with their full routing tables. According to the invention, a KEEPALIVE message is selectively issued to enable the router to detect that each of its neighbors has finished sending all of its routes. After detecting that it has received a full set of routes from each neighbor, the router performs route selection procedures to select the preferred routes and advertises these routes to its neighbors.
Since the invention pertains to restarts of BGP peer connections, the technique involves the use of a first KEEPALIVE message exchanged between BGP neighboring peer routers. In particular, a neighbor does not send a first KEEPALIVE message after a restart until it finishes sending all of its full routing table updates to the router. When the neighbor has no further preferred routes to send, i.e., it has finished sending its full routing table, it may send the first KEEPALIVE message to the router.
Deferring issuance of the first KEEPALIVE message does not violate BGP protocol specification; therefore BGP routers that are configured to implement the invention may advantageously interoperate with routers that do not implement the invention. To avoid deferring route selection indefinitely, the invention further comprises use of a specified timer. That is, a BGP router must perform BGP route selection procedures by the specified time period after restart, even if the router detects that not all of its BGP neighbors have completed sending of their routes to the router.